// scaup
// (c) 2010, Normen Müller, normen.mueller@gmail.com
// $Id: EquivSpec.scala 110 2010-09-12 11:07:58Z normen.mueller $
package scaup.math

import java.text.MessageFormat.{ format }

/** An equivalence specification.
 *  
 *  <p>
 *  For further information please refer to:<br/>
 *  Normen Müller, Change Management on Semi-Structured Documents, PhD thesis,
 *  School of Engineering & Science, Jacobs University Bremen, Campus Ring 1, 28759 Bremen.
 *  </p>
 *  
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 */
class EquivSpec(val name: Symbol, val specification: Map[Symbol, Specification] = Map() withDefault (_ => Deep)) {
  lazy val elements = specification.keys.toList
  
  def requiredAnnotationsOf(e: Symbol) =
    (Set[Symbol]() /: specification(e).alternatives)((s, a) => s ++ (a.requiredAnnotations map (_.id)))
  
  override def hashCode = name.hashCode + specification.hashCode
  
  override def equals(other: Any) = other match {
    case that: EquivSpec =>
      (this eq that) ||
      ((that canEqual this) && this.name == that.name && this.specification == that.specification)
    case _ => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[EquivSpec]
}

// AST ----------------------------------------------------------------------------------

trait Absent

trait Limit

trait Optional

trait Ordered

trait Unordered

sealed abstract class Specification {
  val id: Symbol
  
  val alternatives: List[Alternative]
  
  def +(other: List[Alternative]): Specification
  
  override def hashCode = id.hashCode + alternatives.hashCode
  
  override def equals(other: Any) = other match {
    case that: Specification =>
      (this eq that) ||
      ((that canEqual this) && this.id == that.id && this.alternatives == that.alternatives)
    case _ => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[Specification]
}

//TODO Verify! E.g. evaluation of <code>requiredAnnotationsOf</code> 
case object Deep extends Specification {
  val id = '∗
  
  val alternatives = Alternative(new AllAnnotation with Limit, new AllConstituent with Limit) :: Nil
  
  def +(other: List[Alternative]): this.type = this  
}

final case class Top(alternatives: List[Alternative] = Nil) extends Specification {
  val id: Symbol = '⟙
  
  def +(other: List[Alternative]): Top = Top(alternatives ::: other)
  
  override def canEqual(other: Any) = other.isInstanceOf[Top]
}

final case class Element(id: Symbol, alternatives: List[Alternative] = Nil) extends Specification {
  def +(other: List[Alternative]): Element = Element(id, alternatives ::: other)
  
  override def canEqual(other: Any) = other.isInstanceOf[Element]
}
  
final case class Alternative(
    annotations: Set[AbstractAnnotation] = Set.empty,
    constituents: Set[AbstractConstituent] = Set.empty) {
  lazy val requiredAnnotations: Set[AbstractAnnotation] = annotations -- optionalAnnotations -- absentAnnotations
  
  lazy val optionalAnnotations: Set[AbstractAnnotation] = annotations filter (_.isInstanceOf[Optional])
  
  lazy val absentAnnotations: Set[AbstractAnnotation] = annotations filter (_.isInstanceOf[Absent])
  
  lazy val orderedRequiredConstituent: Set[AbstractConstituent] = Set.empty
  
  lazy val orderedOptionalConstituent: Set[AbstractConstituent] = Set.empty
  
  lazy val unorderedRequiredConstituent: Set[AbstractConstituent] = Set.empty
  
  lazy val unorderedOptionalConstituent: Set[AbstractConstituent] = Set.empty
  
  lazy val absentConstituent: Set[AbstractConstituent] = Set.empty
  
  lazy val limitConstituent: Set[AbstractConstituent] = Set.empty
  
  override def hashCode = annotations.hashCode + constituents.hashCode
  
  override def equals(other: Any) = other match {
    case that: Alternative =>
      (this eq that) ||
      ((that canEqual this) && this.annotations == that.annotations && this.constituents == that.constituents)
    case _ => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[Alternative]
}
  
sealed abstract class AbstractAnnotation {
  val id: Symbol
  
  override def hashCode = id.hashCode
  
  override def equals(other: Any) = other match {
    case that: AbstractAnnotation =>
      (this eq that) ||
      ((that canEqual this) && this.interfaces == that.interfaces && this.id == that.id)
    case _ => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[AbstractAnnotation]
  
  protected def interfaces = getClass.getInterfaces.toSet
}

case class Annotation(id: Symbol) extends AbstractAnnotation {
  override def canEqual(other: Any) = other.isInstanceOf[Annotation]
}

case class AllAnnotation(
    env: {val values: Set[AbstractAnnotation]} = new { val values = Set.empty[AbstractAnnotation] }
) extends AbstractAnnotation with Set[AbstractAnnotation] {  
  self: Set[AbstractAnnotation] =>
  
  val id: Symbol = '_
  
  def contains(elem: AbstractAnnotation): Boolean = env.values contains elem
  def + (elem: AbstractAnnotation): Set[AbstractAnnotation] = new AllAnnotation(new {val values = env.values + elem})
  def - (elem: AbstractAnnotation): Set[AbstractAnnotation] = new AllAnnotation(new {val values = env.values - elem})
  def iterator: Iterator[AbstractAnnotation] = env.values.iterator
  
  override def hashCode = 41 * super.hashCode + env.values.hashCode
  
  override def equals(other: Any) = other match {
    case that: AllAnnotation => super.equals(that) && this.env.values == that.env.values
    case _ => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[AllAnnotation] 
}

case class SomeAnnotation(not: Set[AbstractAnnotation]) extends AbstractAnnotation with Set[AbstractAnnotation] {  
  self: Set[AbstractAnnotation] =>
  
  val id: Symbol = Symbol("\\")
  
  def contains(elem: AbstractAnnotation): Boolean = not contains elem
  def + (elem: AbstractAnnotation): Set[AbstractAnnotation] = new SomeAnnotation(not + elem)    
  def - (elem: AbstractAnnotation): Set[AbstractAnnotation] = new SomeAnnotation(not - elem)
  def iterator: Iterator[AbstractAnnotation] = not.iterator
  
  override def hashCode = 41 * super.hashCode + not.hashCode
  
  override def equals(other: Any) = other match {
    case that: SomeAnnotation => super.equals(that) && this.not == that.not
    case _ => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[SomeAnnotation]
}

/*sealed*/ abstract class AbstractConstituent {
  type T
  
  val id: T
  
  override def hashCode = id.hashCode
  
  override def equals(other: Any) = other match {
    case that: AbstractConstituent =>
      val b = (this eq that) || ((that canEqual this) && this.interfaces == that.interfaces && this.id == that.id)
      b
    case _ => false
  }
  
  def canEqual(other: Any) = other.isInstanceOf[AbstractConstituent]
  
  protected def interfaces = getClass.getInterfaces.toSet
}

case class Constituent(id: Symbol) extends AbstractConstituent {
  type T = Symbol
  
  override def canEqual(other: Any) = other.isInstanceOf[Constituent]  
}

case class TupleConstituent(id: List[AbstractConstituent]) extends AbstractConstituent {
  type T = List[AbstractConstituent]
    
  override def canEqual(other: Any) = other.isInstanceOf[TupleConstituent]
}

case class AllConstituent(
    env: {val values: Set[AbstractConstituent]} = new { val values = Set.empty[AbstractConstituent] }
) extends AbstractConstituent with Set[AbstractConstituent] {
  self: Set[AbstractConstituent] =>
  
  type T = Symbol
  
  val id: Symbol = '_
  
  def contains(elem: AbstractConstituent): Boolean = env.values contains elem
  def + (elem: AbstractConstituent): Set[AbstractConstituent] = new AllConstituent(new {val values = env.values + elem})
  def - (elem: AbstractConstituent): Set[AbstractConstituent] = new AllConstituent(new {val values = env.values - elem})
  def iterator: Iterator[AbstractConstituent] = env.values.iterator
  
  override def hashCode = 41 * super.hashCode + env.values.hashCode
  
  override def equals(other: Any) = other match {
    case that: AllConstituent => super.equals(that) && this.env.values == that.env.values
    case _ => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[AllConstituent]
}  

case class SomeConstituent(not: Set[AbstractConstituent]) extends AbstractConstituent with Set[AbstractConstituent] {
  self: Set[AbstractConstituent] =>
  
  type T = Symbol
  
  val id: Symbol = Symbol("\\")

  def contains(elem: AbstractConstituent): Boolean = not contains elem
  def + (elem: AbstractConstituent): Set[AbstractConstituent] = new SomeConstituent(not + elem)    
  def - (elem: AbstractConstituent): Set[AbstractConstituent] = new SomeConstituent(not - elem)
  def iterator: Iterator[AbstractConstituent] = not.iterator
  
  override def hashCode = 41 * super.hashCode + not.hashCode
  
  override def equals(other: Any) = other match {
    case that: SomeAnnotation => super.equals(that) && this.not == that.not
    case _ => false
  }
  
  override def canEqual(other: Any) = other.isInstanceOf[SomeAnnotation]
}

case class TextConstituent() extends AbstractConstituent {
  type T = Symbol
  
  val id: Symbol = Symbol("<TEXT>")
  
  override def canEqual(other: Any) = other.isInstanceOf[TextConstituent]
}

// parser -------------------------------------------------------------------------------

/** This object provides a simple interface to the equivalence specification parser class.
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
object EquivSpecParser extends Parser {
  def parse(input: String) = phrase(equivspec)(new lexical.Scanner(input)) match {
    case Success(result, _) => result
    case n@_ => error(format("EQ parsing error in\n{0}\n\n", input) + n)
  }
}

import scala.util.parsing.combinator._
import scala.util.parsing.combinator.syntactical._

/** An equivalence specification parser.
 *  @thanks Serge Autexier regarding his fundamental discussions on the EQ syntax.
 *  @thanks Marc Wagner regarding his "limit" idea published in <code>M. Wagner. Change-Oriented Architecture for Mathematical Authoring Assistance. PhD thesis, FR Informatik, Universitaet des Saarlandes, 2010.</code>
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
private[math] class Parser extends StdTokenParsers with ImplicitConversions {
  type Tokens = Lexer
  val lexical: Tokens = new Lexer

  lexical.reserved ++= List(
    "?", "_", "\\", "<TEXT>",
    "alternatives", "annotations", "absent",
    "constituents",
  	"equivspec", "extends", "element",
		"limit",
 		"ordered",
 		"unordered"
  )
  lexical.delimiters ++= List(
    "{", "}",
    "(", ")",
    ","
  )
  
  lazy val equivspec: Parser[EquivSpec] = ("equivspec" ~> name) ~ opt(`extends`) ~ ("{" ~> rep(element | glblmt) <~ "}") ^^ {
    case name ~ Some(upper) ~ specs => error("'extends' not yet supported")
    case name ~ None ~ specs        => new EquivSpec(name, (Map.empty[Symbol,Specification] /: specs)((m,s) => s match {
      case t: Top     => (m get '⟙) match {
        case Some(t) => m + {('⟙, m('⟙) + t.alternatives)}
        case None    => m + {('⟙, t)}
      }        
      case e: Element => (m get e.id) match {
        case Some(e) => m + {(e.id, m(e.id) + e.alternatives)}
        case None    => m + {(e.id, e)}
      }
      case _ => m
    }))
  }
    
  lazy val `extends` = "extends" ~> rep1sep(name, ",")
  
  lazy val element: Parser[Specification] = ("element" ~> ident) ~ ("{" ~> opt(alternatives) <~ "}") ^^ {
    case id ~ Some(alts) => new Element(Symbol(id), alts)
    case id ~ None       => new Element(Symbol(id))
  }

  lazy val glblmt: Parser[Specification] = 
    ( ("limit" ~ "{") ~> rep1(conselem) <~ "}" ^^ {
      case cs => Top(List(Alternative(constituents = ((Set[AbstractConstituent]() /: cs)((s, e) => e match {
        case Constituent(id)       => s + {new Constituent(id) with Limit}
        case TupleConstituent(id)  => s + {new TupleConstituent(id) with Limit}
        case TextConstituent()     => s + {new TextConstituent with Limit}
      })))))
    }
    | ("limit" ~ "{") ~> consallbut <~ "}" ^^ {
      case SomeConstituent(not) => Top(List(Alternative(constituents = new SomeConstituent(not) with Limit)))
      case AllConstituent(env)  => Top(List(Alternative(constituents = new AllConstituent(env) with Limit))) 
    }
    )
  
  lazy val alternatives: Parser[List[Alternative]] =
    ( ("alternatives" ~ "{") ~> rep1("{" ~> altentry <~ "}") <~ "}" ^^ {
      case alts => (List[Alternative]() /: alts.reverse)((l, a) => (new Alternative(a._1, a._2)) :: l)
    }
    | altentry ^^ {
      case alt => List(Alternative(alt._1, alt._2))
    }
    )
  
  lazy val altentry: Parser[(Set[AbstractAnnotation], Set[AbstractConstituent])] =
    ( annotations ~ opt(constituents) ^^ {
      case as ~ Some(cs) => (as, cs)
      case as ~ None     => (as, Set.empty[AbstractConstituent])
    }
    | constituents ~ opt(annotations) ^^ {
      case cs ~ Some(as) => (as, cs)
      case cs ~ None     => (Set.empty[AbstractAnnotation], cs)
    }
    )
    
  lazy val annotations: Parser[Set[AbstractAnnotation]] =
    ( ("annotations" ~ "{") ~> annoallbut ~ rep("," ~> annoentry) <~ "}" ^^ {
      case all ~ as => (all /: as)(_ ++ _)
    }
    | ("annotations" ~ "{") ~> opt(annoentry) <~ "}" ^^ {
      case Some(as) => as
      case None     => Set.empty[AbstractAnnotation]
    }
    )
    
  lazy val annoallbut: Parser[Set[AbstractAnnotation]] =
    "_" ~ opt(("\\" ~ "{") ~> rep1sep(ident, ",") <~ "}") ^^ {
    case all ~ Some(but) => new SomeAnnotation((but map (a => Annotation(Symbol(a)))).toSet)
    case all ~ None      => new AllAnnotation
  }
    
  lazy val annoentry: Parser[Set[AbstractAnnotation]] =
    ( ident ~ opt("?") ~ rep("," ~> annoentry) ^^ {
      case id ~ Some(_) ~ as => (Set[AbstractAnnotation](new Annotation(Symbol(id)) with Optional) /: as)(_ ++ _)
      case id ~ None ~ as    => (Set[AbstractAnnotation](Annotation(Symbol(id))) /: as)(_ ++ _)
    }
    | annoabsent ~ rep("," ~> annoentry) ^^ {
      case abs ~ as => (abs /: as)(_ ++ _)
    }
    )  
  
  lazy val annoabsent: Parser[Set[AbstractAnnotation]] = ("absent" ~ "{") ~> rep1sep(ident, ",") <~ "}" ^^ {
    case as => (as map (a => new Annotation(Symbol(a)) with Absent)).toSet
  }
  
  lazy val constituents: Parser[Set[AbstractConstituent]] = ("constituents" ~ "{") ~> opt(consentry) <~ "}" ^^ {
    case Some(cs) => cs
    case None     => Set.empty[AbstractConstituent]
  }
  
  lazy val consentry: Parser[Set[AbstractConstituent]] =
    ( consabsent ~ rep("," ~> consentry) ^^ {
      case abs ~ cs => (abs /: cs)(_ ++ _)
    }
    | ( "unordered" | "ordered" ) ~ conscoll ~ rep("," ~> consentry) ^^ {
      case "unordered" ~ coll ~ cs => (((Set[AbstractConstituent]() /: coll)((s, e) => e match {
        case a: AllConstituent =>
          s + {new AllConstituent with Ordered}
        case s: SomeConstituent =>
          s + {new SomeConstituent(s.not) with Ordered}
        case c: Constituent => c match {
          case _: Optional => s + {new Constituent(c.id) with Optional with Unordered}
          case _           => s + {new Constituent(c.id) with Unordered}
        } 
        case t: TupleConstituent => t match {
          case _: Optional => s + {new TupleConstituent(t.id) with Optional with Unordered}
          case _           => s + {new TupleConstituent(t.id) with Unordered}  
        }
        case x: TextConstituent => x match {
          case _: Optional => s + {new TextConstituent with Optional with Unordered}
          case _           => s + {new TextConstituent with Unordered}  
        }        
      })) /: cs)(_ ++ _)
      case "ordered" ~ coll ~ cs   => (((Set[AbstractConstituent]() /: coll)((s, e) => e match {
        case a: AllConstituent  =>
          s + {new AllConstituent with Unordered}
        case s: SomeConstituent =>
          s + {new SomeConstituent(s.not) with Unordered}
        case c: Constituent => c match {
          case _: Optional => s + {new Constituent(c.id) with Optional with Ordered}
          case _           => s + {new Constituent(c.id) with Ordered}
        }
        case t: TupleConstituent => t match {
          case _: Optional => s + {new TupleConstituent(t.id) with Optional with Ordered}
          case _           => s + {new TupleConstituent(t.id) with Ordered}
        }
        case x: TextConstituent => x match {
          case _: Optional => s + {new TextConstituent with Optional with Ordered}
          case _           => s + {new TextConstituent with Ordered}
        }
      })) /: cs)(_ ++ _)
    }
    | loclmt ~ rep("," ~> consentry) ^^ {
      case l ~ cs => (l /: cs)(_ ++ _)
    }
    )
    
  lazy val consabsent: Parser[Set[AbstractConstituent]] = ("absent" ~ "{") ~> rep1sep(conselem, ",") <~ "}" ^^ {
    case cs => (Set[AbstractConstituent]() /: cs)((s, e) => (e match {
      case Constituent(id)       => s + {new Constituent(id) with Absent}
      case TupleConstituent(id)  => s + {new TupleConstituent(id) with Absent}
      case TextConstituent()     => s + {new TextConstituent with Absent}
    }))
  } 
  
  lazy val conscoll: Parser[Set[AbstractConstituent]] = 
    ( "{" ~> (consallbut ~ rep("," ~> (conselem ~ opt("?")))) <~ "}" ^^ {      
      case head ~ tail =>
        // here we must not treat AllConstituent and SomeConstituent, respectively, as sets 
        ((head match {
          case a: AllConstituent  => Set[AbstractConstituent](a)
          case s: SomeConstituent => Set[AbstractConstituent](s)
        }) /: tail)((s, e) => e match {
        case Constituent(id) ~ Some(_)       => s + {new Constituent(id) with Optional}
        case TupleConstituent(id) ~ Some(_)  => s + {new TupleConstituent(id) with Optional}
        case TextConstituent() ~ Some(_)     => s + {new TextConstituent with Optional}
        case e ~ None                        => s + e
      })        
//      (head /: tail)((s, e) => e match {
//        case Constituent(id) ~ Some(_)       => s + {new Constituent(id) with Optional}
//        case TupleConstituent(id) ~ Some(_)  => s + {new TupleConstituent(id) with Optional}
//        case TextConstituent() ~ Some(_)     => s + {new TextConstituent with Optional}
//        case e ~ None                        => s + e
//      })
    }
    | "{" ~> (conselem ~ opt("?") ~ rep("," ~> (conselem ~ opt("?")))) <~ "}" ^^ {
      case head ~ tail => (Set[AbstractConstituent]() /: (head ::tail))((s, e) => e match {
        case Constituent(id) ~ Some(_)       => s + {new Constituent(id) with Optional}
        case TupleConstituent(id) ~ Some(_)  => s + {new TupleConstituent(id) with Optional}
        case TextConstituent() ~ Some(_)     => s + {new TextConstituent with Optional}
        case e ~ None                        => s + e
      })
    }
    )
    
  lazy val loclmt: Parser[Set[AbstractConstituent]] = 
    ( ("limit" ~ "{") ~> rep1(conselem) <~ "}" ^^ {
      case cs => (Set[AbstractConstituent]() /: cs)((s, e) => e match {
        case Constituent(id)       => s + {new Constituent(id) with Limit}
        case TupleConstituent(id)  => s + {new TupleConstituent(id) with Limit}
        case TextConstituent()     => s + {new TextConstituent with Limit}
      })
    }
    | ("limit" ~ "{") ~> consallbut <~ "}" ^^ {
      case SomeConstituent(not) => new SomeConstituent(not) with Limit
      case AllConstituent(env)  => new AllConstituent(env) with Limit
    }
    )
    
  lazy val conselem: Parser[AbstractConstituent] = 
    ( ident ^^ { case id => Constituent(Symbol(id)) }
    | "<TEXT>" ^^^ { new TextConstituent }
    | "(" ~> rep1sep(conselem, ",") <~ ")" ^^ { case cs => TupleConstituent(cs) }
    )
    
  lazy val consallbut: Parser[Set[AbstractConstituent]] =
    "_" ~ opt(("\\" ~ "{") ~> rep1sep(conselem, ",") <~ "}") ^^ {
      case all ~ Some(but) => new SomeConstituent(but.toSet)
      case all ~ None      => new AllConstituent
  }

  lazy val name: Parser[Symbol] = ( ident ^^ { case id => Symbol(id) } | string ^^ { case id => Symbol(id) } )  
  
  lazy val string = accept("string", { case lexical.StringLit(n) => n })
}

// lexer --------------------------------------------------------------------------------

import scala.util.parsing.combinator._
import scala.util.parsing.combinator.lexical._
import scala.util.parsing.input.CharArrayReader.EofCh

/** A lexer for an equivalence specification parser.
 *  @author <a href="mailto:normen.mueller@googlemail.com">Normen M&#xFC;ller</a>
 *  @version 0.0.6
 */
private[math] class Lexer extends StdLexical with RegexParsers {
  override type Elem = Char

  override def token =
    ( string ^^ StringLit
    | number ^^ NumericLit
    | delim
    | EofCh ^^^ EOF
    | id ^^ { case i if reserved contains i => Keyword(i) case i => Identifier(i) }
    | '\"' ~> failure("Unterminated string")
    | failure("Illegal character")
    )

  lazy val string =
    ( '\"' ~> rep(charSeq | chrExcept('\"', '\n', EofCh)) <~ '\"' ^^ { _ mkString "" }
    | '\'' ~> rep(charSeq | chrExcept('\'', '\n', EofCh)) <~ '\'' ^^ { _ mkString "" }
    )
    
  lazy val charSeq =
    ( '\\' ~ '\"' ^^^ "\""
    | '\\' ~ '\\' ^^^ "\\"
    | '\\' ~ '/' ^^^ "/"
    | '\\' ~ 'b' ^^^ "\b"
    | '\\' ~ 'f' ^^^ "\f"
    | '\\' ~ 'n' ^^^ "\n"
    | '\\' ~ 'r' ^^^ "\r"
    | '\\' ~ 't' ^^^ "\t"
    | '\\' ~ 'u' ~> unicodeBlock
    )

  lazy val number = """-?(\d+(\.\d*)?|\d*\.\d+)([eE][+-]?\d+)?[fFdD]?""".r

  lazy val id =
    ( '?' ^^^ "?"
    | rep( letter
       | digit
       | elem("underscore", _ == '_')
       | elem("hyphen", _ == '-')
       //| elem("questionmark", _ == '?')
       | elem("backslash", _ == '\\')
       | elem("lbracket", _ == '<')
       | elem("rbracket", _ == '>')
       ) ^^ { _ mkString "" }
    )

  import scala.io.UTF8Codec.{ encode }
  lazy val unicodeBlock = hexDigit ~ hexDigit ~ hexDigit ~ hexDigit ^^ {
    case a ~ b ~ c ~ d => new String(Array(Integer.parseInt(List(a, b, c, d) mkString "", 16)), 0, 1).getBytes("UTF-8")
  }

  lazy val hexDigits = Set[Char]() ++ "0123456789abcdefABCDEF".toArray

  lazy val hexDigit = elem("hex digit", hexDigits.contains(_))
}